//编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性： 
//
// 
// 每行中的整数从左到右按升序排列。 
// 每行的第一个整数大于前一行的最后一个整数。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 3
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 13
//输出：false
// 
//
// 示例 3： 
//
// 
//输入：matrix = [], target = 0
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// m == matrix.length 
// n == matrix[i].length 
// 0 <= m, n <= 100 
// -104 <= matrix[i][j], target <= 104 
// 
// Related Topics 数组 二分查找 
// 👍 285 👎 0

package leetcode.editor.cn;

import common.util.MyUtil;

/**
 * Java：搜索二维矩阵
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P74_SearchA2dMatrix {
    public static void main(String[] args) {
        Solution solution = new P74_SearchA2dMatrix().new Solution();
        int[][] matrix = {
                {1, 3, 5, 7},
                {10, 11, 16, 20},
                {23, 30, 34, 50}
        };
        MyUtil.print(solution.searchMatrix(matrix, 20));
    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 第一行找到目标列，目标列上找到目标行，目标行上找到最终结果
     * T: O(2logN + logM)
     * S: O(1)
     */
    class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
                return false;
            }
            int ROW = matrix.length;
            int COL = matrix[0].length;
            // 第一行找到目标列
            int l1 = 0, r1 = COL - 1;
            while (l1 <= r1) {
                int mid = (r1 - l1 >> 1) + l1;
                if (matrix[0][mid] == target) {
                    return true;
                }
                if (matrix[0][mid] < target) {
                    l1 = mid + 1;
                } else {
                    r1 = mid - 1;
                }
            }
            // 目标列，最右侧的列
            int y = Math.min(Math.max(l1, r1), COL - 1);
            // 目标列上找到目标行
            int l2 = 0, r2 = ROW - 1;
            // 开始在此列查找
            while (l2 <= r2) {
                int mid = (r2 - l2 >> 1) + l2;
                if (matrix[mid][y] == target) {
                    return true;
                }
                if (matrix[mid][y] < target) {
                    l2 = mid + 1;
                } else {
                    r2 = mid - 1;
                }
            }
            // 目标行，最下面的行
            int x = Math.min(Math.max(l2, r2), ROW - 1);
            // 目标行上找到最终结果
            int l3 = 0, r3 = COL - 1;
            // 在此行查询最终结果
            while (l3 <= r3) {
                int mid = (r3 - l3 >> 1) + l3;
                if (matrix[x][mid] == target) {
                    return true;
                }
                if (matrix[x][mid] < target) {
                    l3 = mid + 1;
                } else {
                    r3 = mid - 1;
                }
            }
            return false;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}